package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

/**
 * https://leetcode.com/problems/word-search/
 * see LC212 word search 2
 *
 * @author tzp
 * @since 2020/10/16
 */
public class LC79 implements Backtracking {
    int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) return false;
        boolean[][] path = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean b = backtracking(board, i, j, word, 0, path);
                if (b) return b;
            }
        }
        return false;
    }

    public boolean backtracking(char[][] board, int x, int y, String word, int index, boolean[][] path) {
        if (index == word.length() - 1) {
            return word.charAt(index) == board[x][y];
        } else {
            if (word.charAt(index) == board[x][y]) {
                for (int[] direction : directions) {
                    int newX = x + direction[0];
                    int newY = y + direction[1];
                    if (inArea(board, newX, newY) && !path[newX][newY]) {
                        path[x][y] = true;
                        boolean b = backtracking(board, newX, newY, word, index + 1, path);
                        path[x][y] = false;
                        if (b) return b;
                    }
                }
            }
            return false;
        }
    }

    public boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    public static void main(String[] args) {
        char[][] a = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        System.out.println(new LC79().exist(a, "SEEDD"));
        System.out.println(new LC79().exist(a, "ABCCED"));
        System.out.println(new LC79().exist(new char[][]{{'a', 'a'}}, "aaa"));
    }
}
